package puzzle.projecteuler.p200;

import java.util.List;

import astudy.util.AdvMath.Factors;

public class Problem195C {

	/**
	 *    C = pi/3
	 * => a^2 + b^2 - ab = c^2
	 *    r = (a+b-c)/(2*sqrt(3))
	 * 所以,r <= M <=> a+b-c <= 2*sqrt(3)*M = M'
	 * 如果 a+b-c = m
	 * =>  3ab - 2m(a+b) + m^2 = 0
	 * => (3a-2m)*(3b-2m) = m^2
	 * 我们只要对所有1~M'之间的执行质因数分解，就容易获得答案了。
	 * 
	 * 问题是数据量比较大：
	 * 1、如果直接分解每个m^2，时间上不能通过。这里类似筛法，一次求出所有m^2的分解；
	 * 2、按1描述，大概需要12分钟。进一步，使用该方法求出所有m^2的因子，发现空间不够。（-Xmx1024m）
	 * 
	 * 最终采用了方案1：
	 * 答案是75085391
	 * 花了788250 ms，太慢了。：（
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		
		long s = System.currentTimeMillis();
		System.out.println(T(1053779));
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	public static long T(int m) {
		
		long count = 0; //a+b-c=1的解只有0个
		int M = (int)(m*2*Math.sqrt(3));
		Factors[] tmp = Factors.factor(M);
		for (int i = 2; i <= M; i ++) {
			Factors fs = tmp[i];
			for (Long t: fs.keySet()) {
				fs.put(t, fs.get(t)*2);
			}
		}
		for (int i = 2; i <= M; i ++) {
			List<Factors> t = tmp[i].getAllFactors();
			for (Factors n: t) {
				if (n.longValue() < i) {
					long a3 = n.longValue()+2*i;
					long b3 = (long)i*i/n.longValue() + 2*i;
					if (a3%3 == 0 && b3%3 == 0) {
						count ++;
					}
				} else {
					break;
				}
			}
		}
		return count;
	}
}
